[HAOI2007]-上升序列

传送门

aaaaaaaa我居然不会二分求最长上升/下降子序列！！！

所以今天涨姿势了 qaq

• 题意划重点：字典序最小指 $x_i$ 最小。

先判断下最长上升子序列长度是否 $\geq$ 询问的 $L$。

$O(nm)$ 的复杂度完全可以过，所以我们枚举 $x_i$ 看是否符合条件，若符合则立刻输出 $a_{x_i}$，保证字典序最小。

符合条件是什么意思呢？假设还剩下 $x$ 的长度没有分配，若 $x_i$ 符合要求，则 $x_i$ ~ $n$ 这段中有 $\geq x$ 个后续位置。由于是 $x_i$ ~ $n$ ，我们预处理的是下降而不是上升子序列。

大概是这样：维护最长下降子序列 $b$ 数组，对于每个 $a_i$ 二分求出 $b$ 中第一个 > $a_i$ 的 $b_j$，令 $i$ 位置的后续长度为 $j + 1$.
同时，若 $b[j + 1] < a[i]$, 则令 $b[j + 1] = a[i]$（并不会使子序列更劣，反而有可能更优，因为下降的幅度减小了嘛）

code :

#include <bits/stdc++.h>
#define rep(i, x, y) for (int i = x; i <= y; i++)
using namespace std;

const int N = 1e4 + 10;
int n, m, a[N], x, b[N], f[N], tot;

int query(int x) {
    int l = 1, r = tot, ret = 0;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (b[mid] > x) ret = max(ret, mid), l = mid + 1;
        else r = mid - 1;
    }
    return ret;
}

int main() {
    cin >> n;
    rep(i, 1, n) cin >> a[i];
    for (int i = n; i >= 1; i--) {
        int tmp = query(a[i]);
        f[i] = tmp + 1;
        tot = max(tot, tmp + 1);
        if (b[tmp + 1] < a[i]) b[tmp + 1] = a[i];
    }

    cin >> m;
    while (m--) {
        cin >> x;
        if (x > tot) puts("Impossible");
        else {
            int lst = 0;
            rep(i, 1, n) {
                if (a[i] > lst && f[i] >= x) {
                    printf("%d ", a[i]);
                    x--;
                    lst = a[i];
                    if (!x) break;
                }
            }
            puts("");
        }
    }
    return 0;
}